/*-------------------------------------------------------------------------
 *
 * syncscan.c
 *	  扫描同步支持
 *
 * 当多个后端在同一表上执行顺序扫描时，我们尝试保持它们同步，以减少所需的总体 I/O。目标是
 * 只将每个页面读入共享缓冲区缓存一次，并让所有参与共享扫描的后端在页面退出缓存之前
 * 处理该页面。
 *
 * 由于进行顺序扫描的一组后端中的“领导者”必须等待 I/O，而“跟随者”则不需要，因此一旦我们
 * 能够让后端大致同时检查表的同一部分，就会产生一种强烈的自同步效应。因此，真正需要的
 * 只是让新的后端开始顺序扫描接近于其他后端正在读取的地方。我们可以循环扫描表，从块 X
 * 到结束，然后从块 0 到 X-1，以确保在仍参与公共扫描的同时访问所有行。
 *
 * 为了实现这一点，我们跟踪每个表的扫描位置，并在靠近前一个扫描处开始新的扫描。我们不
 * 尝试进行任何额外的同步来保持扫描在之后的一致；例如，如果结果需要通过慢速网络传输到
 * 客户端，则某些扫描的进展可能会慢得多，我们希望避免这样的查询减慢其他查询的速度。
 *
 * 现实中，任何时候只有几个大型顺序扫描在不同的表上进行。因此，我们仅在一个小的 LRU 列表中
 * 保持扫描位置，并且每次需要查找或更新扫描位置时，都会扫描此列表。整个机制仅适用于
 * 超过阈值大小的表（但这不是本模块的关注点）。
 *
 * 接口例程
 *		ss_get_location		- 返回关系的当前扫描位置
 *		ss_report_location	- 更新当前扫描位置
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/common/syncscan.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/syncscan.h"
#include "miscadmin.h"
#include "storage/lwlock.h"
#include "storage/shmem.h"
#include "utils/rel.h"


/* GUC 变量 */
#ifdef TRACE_SYNCSCAN
bool		trace_syncscan = false;
#endif


/*
 * LRU 列表的大小。
 *
 * 注意：代码假设 SYNC_SCAN_NELEM > 1。
 *
 * XXX：一个好的值是什么？它应该足够大，以容纳同时扫描的
 * 最大数量的大表。但是值越大，开始新的扫描时遍历 LRU 列表的
 * 时间就越长。
 */
#define SYNC_SCAN_NELEM 20

/*
 * 当前扫描位置报告之间的间隔，以页为单位。
 *
 * 注意：这应该小于我们用于批量读取的环大小（见 buffer/freelist.c）。
 * 否则，连接其他扫描的扫描可能会从不再在缓冲区缓存中的页开始。
 * 这有点模糊；无论如何，没有保证新的扫描会在离开缓冲区缓存之前
 * 读取该页，而另一方面该页很可能仍在操作系统缓存中。
 */
#define SYNC_SCAN_REPORT_INTERVAL (128 * 1024 / BLCKSZ)


/*
 * 扫描位置结构本质上是一个双向链表的 LRU，具有头指针和尾指针，
 * 但是设计为在固定大小的共享内存中容纳固定数量的元素。
 */
typedef struct ss_scan_location_t
{
	RelFileNode relfilenode;	/* 关系的标识 */
	BlockNumber location;		/* 在关系中最后报告的位置 */
} ss_scan_location_t;

typedef struct ss_lru_item_t
{
	struct ss_lru_item_t *prev;
	struct ss_lru_item_t *next;
	ss_scan_location_t location;
} ss_lru_item_t;

typedef struct ss_scan_locations_t
{
	ss_lru_item_t *head;
	ss_lru_item_t *tail;
	ss_lru_item_t items[FLEXIBLE_ARRAY_MEMBER]; /* SYNC_SCAN_NELEM 项目 */
} ss_scan_locations_t;

#define SizeOfScanLocations(N) \
	(offsetof(ss_scan_locations_t, items) + (N) * sizeof(ss_lru_item_t))

/* 指向共享内存中的结构的指针 */
static ss_scan_locations_t *scan_locations;

/* 内部函数的原型 */
static BlockNumber fc_ss_search(RelFileNode fc_relfilenode,
							 BlockNumber fc_location, bool fc_set);


/*
 * SyncScanShmemSize --- 报告所需的共享内存空间量
 */
Size SyncScanShmemSize(void)
{
	return SizeOfScanLocations(SYNC_SCAN_NELEM);
}

/*
 * SyncScanShmemInit --- 初始化该模块的共享内存
 */
void SyncScanShmemInit(void)
{
	int			fc_i;
	bool		fc_found;

	scan_locations = (ss_scan_locations_t *)
		ShmemInitStruct("Sync Scan Locations List",
						SizeOfScanLocations(SYNC_SCAN_NELEM),
						&fc_found);

	if (!IsUnderPostmaster)
	{
		/* 初始化共享内存区域 */
		Assert(!fc_found);

		scan_locations->head = &scan_locations->items[0];
		scan_locations->tail = &scan_locations->items[SYNC_SCAN_NELEM - 1];

		for (fc_i = 0; fc_i < SYNC_SCAN_NELEM; fc_i++)
		{
			ss_lru_item_t *fc_item = &scan_locations->items[fc_i];

			/*
			 * 用无效值初始化所有槽。当扫描开始时，
			 * 这些无效条目将从 LRU 列表中移除并用
			 * 真实条目替换。
			 */
			fc_item->location.relfilenode.spcNode = InvalidOid;
			fc_item->location.relfilenode.dbNode = InvalidOid;
			fc_item->location.relfilenode.relNode = InvalidOid;
			fc_item->location.location = InvalidBlockNumber;

			fc_item->prev = (fc_i > 0) ?
				(&scan_locations->items[fc_i - 1]) : NULL;
			fc_item->next = (fc_i < SYNC_SCAN_NELEM - 1) ?
				(&scan_locations->items[fc_i + 1]) : NULL;
		}
	}
	else
		Assert(fc_found);
}

/*
 * ss_search --- 在 scan_locations 结构中查找给定 relfilenode 的条目。
 *
 * 如果 "set" 为真，则位置更新为给定位置。如果未找到给定
 * relfilenode 的条目，它将在列表头部创建，位置为给定位置，
 * 即使 "set" 为假。
 *
 * 在任何情况下，返回可能更新后的位置。
 *
 * 调用者负责对共享数据结构进行适当的锁定。
 */
static BlockNumber fc_ss_search(RelFileNode fc_relfilenode, BlockNumber fc_location, bool fc_set)
{
	ss_lru_item_t *fc_item;

	fc_item = scan_locations->head;
	for (;;)
	{
		bool		fc_match;

		fc_match = RelFileNodeEquals(fc_item->location.relfilenode, fc_relfilenode);

		if (fc_match || fc_item->next == NULL)
		{
			/*
			 * 如果我们到达列表末尾而未找到匹配项，则接管
			 * 最后一个条目
			 */
			if (!fc_match)
			{
				fc_item->location.relfilenode = fc_relfilenode;
				fc_item->location.location = fc_location;
			}
			else if (fc_set)
				fc_item->location.location = fc_location;

			/* 将条目移动到 LRU 列表的前面 */
			if (fc_item != scan_locations->head)
			{
				/* 断开链接 */
				if (fc_item == scan_locations->tail)
					scan_locations->tail = fc_item->prev;
				fc_item->prev->next = fc_item->next;
				if (fc_item->next)
					fc_item->next->prev = fc_item->prev;

				/* 链接 */
				fc_item->prev = NULL;
				fc_item->next = scan_locations->head;
				scan_locations->head->prev = fc_item;
				scan_locations->head = fc_item;
			}

			return fc_item->location.location;
		}

		fc_item = fc_item->next;
	}

	/* 未到达 */
}

/*
 * ss_get_location --- 获取扫描的最佳起始位置
 *
 * 返回关系上顺序扫描的最后报告位置，如果未找到有效位置则返回 0。
 *
 * 我们期望调用者刚刚执行了 RelationGetNumberOfBlocks()，
 * 因此该数字被传入，而不再重新计算。结果保证小于 relnblocks
 * （假设大于 0）。
 */
BlockNumber ss_get_location(Relation fc_rel, BlockNumber fc_relnblocks)
{
	BlockNumber fc_startloc;

	LWLockAcquire(SyncScanLock, LW_EXCLUSIVE);
	fc_startloc = fc_ss_search(fc_rel->rd_node, 0, false);
	LWLockRelease(SyncScanLock);

	/*
	 * 如果位置不是此扫描的有效块编号，则从 0 开始。
	 *
	 * 如果例如 VACUUM 在保存位置后截断了表，这可能会发生。
	 */
	if (fc_startloc >= fc_relnblocks)
		fc_startloc = 0;

#ifdef TRACE_SYNCSCAN
	if (trace_syncscan)
		elog(LOG,
			 "SYNC_SCAN: start \"%s\" (size %u) at %u",
			 RelationGetRelationName(fc_rel), fc_relnblocks, fc_startloc);
#endif

	return fc_startloc;
}

/*
 * ss_report_location --- 更新当前扫描位置
 *
 * 在共享的 Sync Scan 状态中写入一条形式为
 * (relfilenode, blocknumber) 的条目，覆盖任何现有的
 * 同一 relfilenode 的条目。
 */
void ss_report_location(Relation fc_rel, BlockNumber fc_location)
{
#ifdef TRACE_SYNCSCAN
	if (trace_syncscan)
	{
		if ((fc_location % 1024) == 0)
			elog(LOG,
				 "SYNC_SCAN: scanning \"%s\" at %u",
				 RelationGetRelationName(fc_rel), fc_location);
	}
#endif

	/*
	 * 为了减少锁争用，每 N 页仅报告一次扫描进度。出于同样的原因，
	 * 如果锁不可立即获取，则不进行阻塞。
	 * 丢失一些更新并不重要，这只是意味着一个想要加入队列的新扫描
	 * 将稍微落后于扫描的当前进度。希望页面仍在操作系统缓存中，
	 * 并且扫描能够快速赶上。
	 */
	if ((fc_location % SYNC_SCAN_REPORT_INTERVAL) == 0)
	{
		if (LWLockConditionalAcquire(SyncScanLock, LW_EXCLUSIVE))
		{
			(void) fc_ss_search(fc_rel->rd_node, fc_location, true);
			LWLockRelease(SyncScanLock);
		}
#ifdef TRACE_SYNCSCAN
		else if (trace_syncscan)
			elog(LOG,
				 "SYNC_SCAN: missed update for \"%s\" at %u",
				 RelationGetRelationName(fc_rel), fc_location);
#endif
	}
}
